#include <iostream>
#include <vector>

using namespace std;
template <typename T>
class heap_data{
    public:
        T data;
        double key;
};

template<typename T>
class M_Heap
{
private:
    vector<heap_data<T>> data;
    void adjust_heap(int node,int size);
    void heap_sort();
    bool smallOrBig=true;//最小堆是true,最大堆是false
public:
    M_Heap(bool smallHeap);
    ~M_Heap();
    void addData(heap_data<T> d);
    heap_data<T> getTop();
    heap_data<T> pop();
};

template<typename T> M_Heap<T>::M_Heap(bool smallHeap){
    smallOrBig=smallHeap;
}
template<typename T> M_Heap<T>::~M_Heap(){

}
template<typename T> void M_Heap<T>::adjust_heap(int node,int size){

     int left = 2*node + 1;
        int right = 2*node + 2;
        int max = node;
        if( left < size && (data[left].key> data[max].key)==smallOrBig)
                max = left;
        if( right < size && (data[right].key > data[max].key)==smallOrBig)
                max = right;
        if(max != node)
        {
                swap( data[max], data[node]);
                adjust_heap(max, size);
        }
}

template<typename T> void M_Heap<T>::heap_sort(){
    int len=data.size();
    for(int i = len/2 -1; i >= 0; --i)
                adjust_heap(i,len);
 
        for(int i = len - 1; i >= 0; i--)
        {
                swap(data[0], data[i]);           // 将当前最大的放置到数组末尾
                adjust_heap(0 , i);              // 将未完成排序的部分继续进行堆排序
        }

}

template<typename T> void M_Heap<T>::addData(heap_data<T> d){
    data.insert(data.end(),d);
    heap_sort();
}
template<typename T> heap_data<T> M_Heap<T>::getTop(){
    return data.at(0);
}
template<typename T> heap_data<T> M_Heap<T>:: pop(){
    heap_data result=data.at(0);
    swap(data[0],data.at(data.size()-1));
    data.pop_back();
    heap_sort();
    // for(int i=0;i<data.size();i++){
    //     data.at(i).key++;
    // }
    return result;
}